/**
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * <p>
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * <p>
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：x = 4
 * 输出：2
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 0 <= x <= 2³¹ - 1
 * <p>
 * <p>
 * Related Topics 数学 二分查找 👍 1177 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID00069Sqrtx {
    public static void main(String[] args) {
        Solution solution = new ID00069Sqrtx().new Solution();

        System.out.println(solution.mySqrt(2147395600));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int mySqrt(int x) {
            if (x == 0) return 0;
            int maxSqrt = (int) Math.sqrt(Integer.MAX_VALUE);
            if (x >= maxSqrt * maxSqrt) return maxSqrt;
            int left = 1;
//        int right = ;
            int right = x;


            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (mid > maxSqrt) mid = maxSqrt;
                if (mid * mid == x || ((mid * mid) < x && ((mid + 1) * (mid + 1)) > x)) {
                    return mid;
                } else if (x < mid * mid) {
                    right = mid - 1;
                } else if (mid * mid < x) {
                    left = mid + 1;
                }


            }


            return 0;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}